#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>  // 系统错误码
#include "linklist.h"

// 初始化一个不带头节点空链表
// head --> NULL
linklist init_list(void)
{
    linklist head=malloc(sizeof(linklist));
    if(head!==NULL)
    {
        head->next=NULL;
    } 
    return head;
}

// 新建节点
linklist new_node(int data)
{
    linklist new = malloc(sizeof(listnode));
    if(new != NULL)
    {
        new->data = data;
        new->next = NULL;
    }
    return new;
}

bool is_empty(linklist head)
{
    return head == NULL;
}

// 尾插法新增节点
void list_add_tail(linklist *phead, linklist new)
{
    // 如果链表本身为空，则new成为链表第一个节点
    if(is_empty(*phead))
    {
        *phead = new;
        return;
    }

    // 找到尾指针
    linklist tail;
    for(tail=*phead; tail->next!=NULL; tail=tail->next);

    // 更新尾结点
    tail->next = new;
}

// 返回指定数据data的上一个节点的指针
// 若指定数据data在链表首位，则返回NULL
// 若没有指定数据data，则返回NULL
linklist find_prev_node(linklist head, int data)
{
    if(is_empty(head))
        return NULL;
    
    // 若指定数据data在链表首位，则返回NULL
    if(head->data == data)    
        return NULL;
    
    linklist prev; // 指向data上一个节点
    linklist p;    // 指向data节点
    for(prev=head, p=head->next; p!=NULL; p=p->next)
    {
        if(p->data == data)
            return prev;
        
        prev = p;
    }

    // 若没有指定数据data，则返回NULL
    return NULL;
}

// 剔除指定数据的节点
linklist list_del(linklist *phead, int data)
{
    // 特殊情况一：链表为空
    if(is_empty(*phead))
        return NULL;

    // 特殊情况二：链表的第一个节点刚好就是要剔除的节点
    if((*phead)->data == data)
    {
        // 保留原来的头指针
        linklist tmp = *phead;

        // 将实参head指向下一个节点（可能是NULL）
        // *phead = ((*phead)->next==NULL ? NULL : (*phead)->next);
        *phead = (*phead)->next;
        // 令要剔除的节点next置空并将之返回，给调用者处理
        tmp->next = NULL;
        return tmp;
    }


    // 一般情况：
    // ① 找到要删除的节点的前一个节点指针k
    linklist k = find_prev_node(*phead, data);
    if(k == NULL)
        return NULL;

    // ② 将k绕过要剔除的节点
    linklist p = k->next;
    k->next = p->next;

    // ③ 孤立节点p，令其next指针为NULL
    p->next = NULL;

    // ④ 返回已剔除节点指针p给调用者处理
    return p;
}

// 遍历
void show_list(linklist head)
{
    head=head->next;
    if(is_empty(head))
        return;
    
    for(linklist p=head; p!=NULL; p=p->next)
        printf("%d\t", p->data);
    printf("\n");
}